/*
Date:20210502 11:48AM
key:自己的写法通过78/87。通过增长测了单位来算。
    然而聪明做法是逐层累加得出所有间隙，通过hash检测间隙出现次数，出现最多的那个间隙用size去减即可。
*/
class Solution {
public:
    // bool throughlayer(int d,vector<int>&v)
    // {
    //     for(int j:v)
    //     {
    //         //cout<<d<<" "<<j<<endl;
    //         if(d>j){d-=j;continue;}
    //         if(d==j){return 0;}
    //         if(d<j){return 1;}
    //     }
    //     return 1;
    // }
    int leastBricks(vector<vector<int>>& wall)
    {
        // //墙宽
        // int kuan=accumulate(wall[0].begin(),wall[0].end(),0);
        // //找最小单位
        // int min1=INT_MAX;
        // //int max1=INT_MIN;
        // for(vector<int>v:wall)
        // {
        //     int tmp=*min_element(v.begin(),v.end());
        //     min1=min(min1,tmp);
        //     //tmp=*max_element(v.begin(),v.end());
        //     //max1=max(max1,tmp);
        // }
        // //每个单位去测量一次
        // int min2=wall.size();//最多就是全穿过
        // for(int i=min1;i<kuan;i+=min1)//这里应该每次增加最小单位
        // {
        //     int tmp=0;
        //     for(vector<int>v:wall)
        //     {
        //         if(throughlayer(i,v))//如果穿过，则+1
        //         {
        //             tmp++;
        //         }
        //     }
        //     min2=min(min2,tmp);
        //     //cout<<i<<" "<<tmp<<" "<<endl;
        // }
        unordered_map<int,int>m;
        for(vector<int>v:wall)
        {
            int tmp=0;
            for(int j=0;j<v.size()-1;j++)
            {
                tmp+=v[j];
                auto t=m.find(tmp);
                if(t!=m.end()){t->second++;}
                else
                {
                    m.insert(pair<int,int>(tmp,1));
                }
                //cout<<tmp;
            }
            
        }
        int max1 = 0;
        for(pair<int,int>p:m)
        {
            
            max1=max(max1,p.second);
            
        }
        return wall.size()-max1;
    }
};